#include <iostream>
#include <climits> // 用于INT_MAX
using namespace std;

#define MAX_VERTEX 100  // 最大顶点数
#define INF INT_MAX     // 代表无穷大

// 邻接矩阵图结构
struct MGraph {
    int** arc;         // 邻接矩阵（存储权值）
    int vertexNum;      // 顶点数
};

// 最小生成树辅助结构
struct MSTEdge {
    int lowcost;    // 当前顶点到MST的最小权值
    int adjvex;     // 该顶点在MST中的邻接点
};

// 寻找当前最小权值边
int minEdge(MSTEdge* shortEdge, int n) {
    int minVal = INF;
    int minIndex = -1;
    for (int i = 0; i < n; ++i) {
        if (shortEdge[i].lowcost > 0 && shortEdge[i].lowcost < minVal) {
            minVal = shortEdge[i].lowcost;
            minIndex = i;
        }
    }
    return minIndex;
}

// Prim算法实现
void Prim(MGraph G, int start) {
    MSTEdge* shortEdge = new MSTEdge[G.vertexNum];
    
    // 初始化辅助数组
    for (int i = 0; i < G.vertexNum; ++i) {
        shortEdge[i].lowcost = (G.arc[start][i] == 0) ? INF : G.arc[start][i];
        shortEdge[i].adjvex = start;
    }
    shortEdge[start].lowcost = 0;  // 起点加入集合U

    // 构建n-1条边
    for (int i = 0; i < G.vertexNum - 1; ++i) {
        int k = minEdge(shortEdge, G.vertexNum);
        if (k == -1) break;  // 处理非连通图情况

        // 输出生成的边
        cout << shortEdge[k].adjvex << "-" << k 
             << "\tweight: " << shortEdge[k].lowcost << endl;

        shortEdge[k].lowcost = 0;  // 顶点k加入集合U

        // 更新其他顶点的lowcost
        for (int j = 0; j < G.vertexNum; ++j) {
            if (G.arc[k][j] != 0 && G.arc[k][j] < shortEdge[j].lowcost) {
                shortEdge[j].lowcost = G.arc[k][j];
                shortEdge[j].adjvex = k;
            }
        }
    }
    delete[] shortEdge;
}

int main() {
    system("chcp 65001"); // 中文编码设置
    // 创建示例图（与Prim算法示例相同结构）
    MGraph G;
    G.vertexNum = 5;
    
    // 初始化邻接矩阵（0表示无直接连接）
    G.arc = new int*[5]{
        new int[5]{0, 2, 0, 6, 0},
        new int[5]{2, 0, 3, 8, 5},
        new int[5]{0, 3, 0, 0, 7},
        new int[5]{6, 8, 0, 0, 9},
        new int[5]{0, 5, 7, 9, 0}
    };

    cout << "最小生成树构建过程：" << endl;
    Prim(G, 0);  // 从顶点0开始生成

    // 释放内存
    for (int i = 0; i < 5; ++i) delete[] G.arc[i];
    delete[] G.arc;
    
    return 0;
}